#include "Tree.h"

//前序遍历（深度优先遍历）
void PreOrder(PBTree root)
{
    if(NULL == root)
    {
        return;
    }
    printf("%c ",root->data);
    PreOrder(root->left_child);
    PreOrder(root->right_child);
}

//中序遍历
void InOrder(PBTree root)
{
    if(NULL == root)
    {
        return;
    }
    InOrder(root->left_child);
    printf("%c ",root->data);
    InOrder(root->right_child);
}

//后序遍历
void PostOrder(PBTree root)
{
    if(NULL == root)
    {
        return;
    }
    PostOrder(root->left_child);
    PostOrder(root->right_child);
    printf("%c ",root->data);
}

//层序遍历
void LeverOrder(PBTree root)
{
    //创建链表
    LinkQueue lq;
    Queue_init(lq);
    //记录出队列的结点
    ElemType2 p;
    //入队列
    enQueue(lq,root);
    while(!Queue_empty(lq))
    {
        deQueue(lq,p);
        printf("%c ",p->data);
        if(p->left_child)
        {
            enQueue(lq,p->left_child);
        }
        if(p->right_child)
        {
            enQueue(lq,p->right_child);
        }
    }
}

//计算wpl
int wpl_pre_order(PBTree root,int deep)
{
    static int wpl=0;
    if(NULL != root)
    {
        if (root->left_child == NULL && root->right_child == NULL)
        {
            wpl += root->data * deep;
        }
        wpl_pre_order(root->left_child, deep + 1);
        wpl_pre_order(root->right_child, deep + 1);
    }
    return wpl;
}

int WPL(PBTree root)
{
    return wpl_pre_order(root,0);
}


int main() {
    PBTree root=NULL; //建立根结点指针
    PBTree pNode;     //创建新的树结点的指针
    ElemType c;       //要插入的元素
    //创建辅助队列的头尾指针和当前插入结点指针
    PQueue pcur,ptail;
    while(scanf("%c",&c))
    {
        if('\n' == c){
            break;
        }
        //给树申请一个结点
        pNode=(PBTree)calloc(1,sizeof(BTree));
        pNode->data=c;
        //给队列申请一个空间，并将新结点进队列
        PQueue pqueu=(PQueue)calloc(1,sizeof(Queue));
        pqueu->tnode=pNode;
        //判断树当前是否为NULL
        if(NULL == root)
        {
            root=pNode;
            ptail=pcur=pqueu;
        }
        else{
            ptail->next=pqueu;     //队列结点链接上队列
            ptail=pqueu;           //改变尾指针
            if( NULL == pcur->tnode->left_child)
            {
                pcur->tnode->left_child=pNode;  //新节点连接在父节点的左子树
            }
            else //NULL == pcur->tnode->right_child
            {
                pcur->tnode->right_child=pNode; //新节点连接在父节点的右子树
                pcur=pcur->next;         //当前结点父节点左右孩子均不为空，则移动队列结点
            }
        }
    }
    printf("--------------PreOrder----------------\n");
    PreOrder(root);
    printf("\n---------------InOrder----------------\n");
    InOrder(root);
    printf("\n--------------PostOrder----------------\n");
    PostOrder(root);
    printf("\n--------------LeverOrder----------------\n");
    LeverOrder(root);
    printf("\n--------------WPL----------------\n");
    printf("%d", WPL(root));
    return 0;
}
